Decyclic 3-connected cubic graphs
Roman Nedela

Abstract

A set of vertices of a graph G is said to be decycling if its removal 
leaves an acyclic subgraph. The size of a smallest decycling set is the 
decycling number of G. Generally, at least ceil((n + 2)/4) vertices have to 
be removed in order to decycle a cubic graph on n vertices. In 1979, 
Payan and Sakarovitch proved that the decycling number of a cyclically 
4-edge-connected cubic graph of order n equals ceil((n + 2)/4). In addition, 
they characterised the structure of minimum decycling sets and their 
complements. If n = 2 (mod 4), then G has a decycling set which is 
independent and its complement induces a tree. If n = 0 (mod 4), then 
one of two possibilities occurs: either G has an independent decycling 
set whose complement induces a forest of two trees, or the decycling set 
is near-independent (which means that it induces a single edge) and its 
complement induces a tree. We strengthen the result of Payan and 
Sakarovitch by proving that the latter possibility (a near-independent 
set and a tree) can always be guaranteed. Moreover, we relax the 
assumption of cyclic 4-edge-connectivity to significantly weaker odd 
cyclic 3-edge-connectivity. We also discuss a somewhat surprising 
relationship between the decycling number and the maximum genus of a 
cubic graph, which is in the background of most of our present results.

Joint work with M. Seifrtova and M. Skoviera.